package com.atguigui.leetcode;

/**
 * OfferII P029.排序的循环链表
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/6/18 8:38
 */
public class POfferII029FourUeAj6 {
    public static void main(String[] args) {
        Solution solution = new POfferII029FourUeAj6().new Solution();

        Node node1 = new Node(3);
        Node node2 = new Node(4);
        Node node3 = new Node(1);

        node1.next = node2;
        node2.next = node3;
        node3.next = node1;


        solution.insert(node1, 2);

        // TO TEST
    }

    class Solution {
        public Node insert(Node head, int insertVal) {

            Node node = new Node(insertVal);
            //如果循环链表为空，则插入一个新节点并将新节点的 next 指针指向自身
            if (head == null) {
                node.next = node;
                return node;
            }
            //如果循环链表的头节点的 next 指针指向自身，则循环链表中只有一个节点
            if (head.next == head) {
                head.next = node;
                node.next = head;
                return head;
            }

            //如果循环链表中的节点数大于 11，则需要从头节点开始遍历循环链表，寻找插入新节点的位置，使得插入新节点之后的循环链表仍然保持有序。
            Node curr = head, next = head.next;
            while (next != head) {
                // 找到位置
                if (insertVal >= curr.val && insertVal <= next.val) {
                    break;
                }
                if (curr.val > next.val) {
                    if (insertVal > curr.val || insertVal < next.val) {
                        break;
                    }
                }

                //指针变化
                curr = curr.next;
                next = next.next;
            }

            //插入数据
            curr.next = node;
            node.next = next;
            return head;
        }
    }


}

class Node {
    public int val;
    public Node next;

    public Node() {
    }

    public Node(int val) {
        this.val = val;
    }

    public Node(int _val, Node _next) {
        this.val = _val;
        this.next = _next;
    }
}
